package _02_linked_list.exerc.merge;

import _02_linked_list.exerc.ListNode;
import _02_linked_list.exerc.ListNodeBuilder;
import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/3 - 16:43
 * 合并两个有序的链表
 * <p>
 * [1,2] [1,3]  = [1,1,1,2,3]
 * [] []  = []
 * [] [1] = [1]
 */
public class MyTest {
    @Test
    public void test() {
        ListNode list1 = ListNodeBuilder.of(new int[]{1, 1, 2});
        ListNode list2 = ListNodeBuilder.of(new int[]{1, 3, 12});

//        System.out.println(foo1(list1, list2));
        System.out.println(foo2(list1, list2));
    }

    /**
     * 方式1
     * 谁小，就把谁链给p，p 和小的都向后平移一位
     * 当p1、p2 有一个为 null，退出循环，把不为 null 的再链给 p
     *
     * @param list1
     * @param list2
     * @return
     */
    ListNode foo1(ListNode list1, ListNode list2) {
        ListNode s = new ListNode();
        /*
            s 表示创建的新链表，存储 list1 + list2 合并的数据
            p 表示 s 中最后一个非空元素下标，下次插入直接指定 p.next
         */
        ListNode p = s;
        ListNode p1 = list1;
        ListNode p2 = list2;

        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }

//        while (p1 != null && p2 != null) {
//            if (p1.val <= p2.val) {
//                p.next = p1;
//                p1 = p1.next;
//                p = p.next;
//            }
//            if(p1 == null) {
//                p.next = p2;
//                p2 = null;
//                break;
//            }
//            if (p1.val >= p2.val) {
//                p.next = p2;
//                p2 = p2.next;
//                p = p.next;
//            }
//        }
//        if (p1 != null) {
//            p.next = p1;
//        }
//        if (p2 != null) {
//            p.next = p2;
//        }
        return s.next;
    }

    // 方式2 递归
    ListNode foo2(ListNode list1, ListNode list2) {
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }
        /*
        list1   [1, 1, 2]
        list2   [1, 3, 12]
         */

        if(list1.val < list2.val) {
            list1.next = foo2(list1.next, list2);
            return list1;
        } else {
            list2.next = foo2(list1, list2.next);
            return list2;
        }
    }
}
